import type { IStructureItem } from '../type'

/**
 * @author hzq
 * @description 双端队列
 * @date 2024-11-03
 */
class Deque<T> {
  private items: IStructureItem<T>
  private lowestCount: number
  private count: number
  constructor() {
    this.items = {}
    this.lowestCount = 0
    this.count = 0
  }

  /**
   * 向队列尾部添加元素
   * @param element 要添加的元素
   * @returns
   */
  addTail(element: T) {
    this.items[this.count++] = element
    return this.size
  }

  /**
   * 向队列头部添加元素
   * @param element 要添加的元素
   * @returns
   */
  addHead(element: T) {
    // 如果队列为空，则调用addTail方法添加元素
    if (this.count === 0) {
      this.addTail(element)
      // 如果队列中有元素，且最低计数大于0，则将元素添加到最低计数位置
    } else if (this.lowestCount > 0) {
      this.items[--this.lowestCount] = element
      // 如果队列中有元素，且最低计数等于0，则将元素添加到队列头部
    } else {
      for (let i = this.count; i > this.lowestCount; i--) {
        this.items[i] = this.items[i - 1]
      }
      this.count++
      this.items[0] = element
    }
    // 返回队列大小
    return this.size
  }

  /**
   * 删除并返回队列尾部的元素
   * @returns 删除的元素
   */
  getTail() {
    if (this.isEmpty()) return void 0
    this.count--
    const result = this.items[this.count]
    delete this.items[this.count]
    return result
  }

  /**
   * 双端队列中取出头部元素
   * @returns 删除的元素
   */
  getHead() {
    if (this.isEmpty()) return void 0
    return this.items[this.lowestCount++]
  }

  /**
   * 查看队列头部元素
   * @returns
   */
  peekHead() {
    if (this.isEmpty()) return void 0
    return this.items[this.lowestCount]
  }

  /**
   * 查看尾部元素
   * @returns
   */
  peekTail() {
    if (this.isEmpty()) return void 0
    return this.items[this.count - 1]
  }

  isEmpty() {
    return this.size == 0
  }

  get size() {
    return this.count - this.lowestCount
  }

  toString(): string {
    if (this.isEmpty()) {
      return ''
    }
    //@ts-ignore
    let res = this.items[this.lowestCount].toString()
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      //@ts-ignore
      res = `${res}, ${this.items[i].toString()}`
    }
    return res
  }
}

export default Deque
